package com.sunny.l73;

import java.util.HashMap;

/**
 * @Author zsunny
 * @Date 2018/9/23 19:36
 * @Mail zsunny@yeah.net
 */
public class Solution {

    HashMap<Character, Integer> map = new HashMap<>();

    public String minWindow(String S, String T) {
        if(null == S || null == T){
            return "";
        }
        for(int i=0;i<T.length();i++){
            if(map.containsKey(T.charAt(i))){
                map.put(T.charAt(i), map.get(T.charAt(i))+1);
            }else{
                map.put(T.charAt(i), 1);
            }
        }
        int left = 0;
        int right = 0;
        int cnt = 0;
        int minLen = S.length() + 1;
        String res = "";
        for(; right<S.length(); right++){
            if(map.containsKey(S.charAt(right))){
                map.put(S.charAt(right), map.get(S.charAt(right))-1);
                if(map.get(S.charAt(right)) > 0){
                    cnt++;
                }
                while (cnt == T.length()){
                    if(map.containsKey(S.charAt(left))){
                        if(right-left+1 < minLen){
                            minLen = right - left + 1;
                            res = S.substring(left, right+1);
                        }
                        map.put(S.charAt(left), map.get(S.charAt(left))+1);
                        if(map.get(S.charAt(left)) > 0){
                            cnt--;
                        }
                    }
                    left++;
                }
            }
        }
        return res;
    }
}